package leetcode.editor.vscdev.hot100;

public class lc5 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "babad";
        String res = solution.longestPalindrome(s);
        System.out.println(res);
    }
}

class Solution {
    public String longestPalindrome(String s) {
        // 依次枚举中心，以中心出发左右指针判断是否为回文子串
        if (s==null || s.length() == 1){
            return s;
        }
        char[] arr = s.toCharArray();
        int lenMax = 0;
        int startIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            // 注意以整个串的长度要判断奇数偶数是错误的
            // 奇数回文子串判断
            int l = i,r = i;
            while (l >= 0 && r <= arr.length - 1 && arr[l] == arr[r]) {
                if (r-l+1>lenMax) {
                    lenMax = r-l+1;
                    startIndex = l;
                }
                l--;r++;
            }
            // 偶数回文子串判断
            l = i;r = i + 1;
            while (l >= 0 && r <= arr.length - 1 && arr[l] == arr[r]) {
                if (r-l+1>lenMax) {
                    lenMax = r-l+1;
                    startIndex = l;
                }
                l--;r++;
            }
        }
        return s.substring(startIndex, startIndex+lenMax);// 左闭右开
    }

    public String longestPalindromeDP(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int n = s.length();
        // dp[i][j] 表示 s.substring(i, j+1) 是否为回文串
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        int begin = 0;
        
        // 单个字符都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        char[] chars = s.toCharArray();
        
        // 枚举子串长度（从2开始）
        for (int len = 2; len <= n; len++) {
            // 枚举左边界
            for (int i = 0; i < n; i++) {
                // 计算右边界
                int j = i + len - 1;
                // 右边界越界
                if (j >= n) {
                    break;
                }
                // 判断是否为回文
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    // 长度为2或3的子串，只需比较两端字符
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 状态转移：两端字符相等且去掉两端后的子串也是回文
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 更新最长回文子串信息
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
